#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>

using namespace std;

const int N = 2e5 + 10, M = 19;

int n, m;
int st[N][M];
int q[N];

void init(){
    for(int j = 0; j < M; j ++){
        for(int i = 1; i + (1 << j) - 1 <= n; i ++){
            if(!j) st[i][j] = q[i];
            else st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
}


int query(int l, int r){
    int len = r - l + 1;
    int k = log(len) / log(2);
    
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}


int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> q[i];
        // exit(0);
    init();

    
    cin >> m;
    while(m--){
        int a, b;
        cin >> a >> b;
        cout << query(a, b) << '\n';
    }
    return 0;
}
